package leetcode;

import util.ListNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0142.java
 * @Author : WangRuoyu
 * @Date 2023/11/7 22:45
 */


public class Q0142 {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode quick = head.next;
        ListNode slow = head;
        while (true) {
            if (quick == slow) break;
            if (quick == null || quick.next == null) return null;
            slow = slow.next;
            quick = quick.next.next;
        }
        slow = head;
        quick = quick.next;
        while (true) {
            if (quick == slow) return slow;
            quick = quick.next;
            slow = slow.next;
        }
    }

    //    public ListNode detectCycle(ListNode head) {
//        HashSet<ListNode> set = new HashSet<>();
//        while (head != null) {
//            if (set.contains(head)) return head;
//            set.add(head);
//            head = head.next;
//        }
//        return null;
//    }
    public static void main(String[] args) {
        Q0142 sl = new Q0142();
    }
}